/**
 * 有链表c[a1,b1,a2,b2,a3,b3.....]
 * 要求在原地将这个量表拆成a[a1,a2,a3,a4...]和b[bn,bn-1,bn-2,bn-3...]
 * 这里的b是逆序的 
 */

#include"LinkedList.h"

/**
 * 头插法的最终顺序和插入顺序是相反的
 * 尾插法的最终顺序和插入顺序是相同的P
 * 访问到a_i的时候使用尾插法插入到a节点
 * 方位到b_i的时候使用头发插法插入到b
 */
LinkedList* divide(LinkedList *c){
    LinkedList *b=new LinkedList();//b是第二个链表
    b->next=nullptr;
    LinkedListNode *p=c->next,*q;//p是工作指针
    LinkedListNode *ra=c;//ra永远指向c的尾节点
    while (p!=nullptr)
    {
        ra->next=p;ra=p;//对于ra这个链表（就是c，也是最终的a，使用尾插）
        p=p->next;//p后移一位
        if(p!=nullptr){//如果p移动之后不为空，那么就是b_i
            q=p->next;//保存p的下一个，即下一个a_i
            p->next=b->next;//p节点头插到b中(此时p的前驱有两个，一个是b链表的，还有一个是a的，但是在下一次循环的时候，a的next就会指向别的元素，从而和p断开)
            b->next=p;
            p=q;
        }
    }
    ra->next=nullptr;
    return b;

}
